package 复习.博客2.递归和回溯;

import java.util.ArrayList;
import java.util.Arrays;

public class 字符串的排列 {
    ArrayList<String> lists = new ArrayList<>();
    public ArrayList<String> Permutation (String str) {
        // write code here
        char[] arr = str.toCharArray();
        boolean[] flag = new boolean[arr.length];
        Arrays.fill(flag,false);
        Arrays.sort(arr);
        backStacking(arr,flag);
        return lists;
    }

    StringBuilder str = new StringBuilder();
    public void backStacking(char[] arr,boolean[] flag){
        if(str.length() == arr.length){
            lists.add(str.toString());
        }
        for (int i = 0; i < arr.length; i++) {
            if(i > 0 && arr[i] == arr[i - 1] && flag[i - 1] == false){
                continue;
            }
            if(flag[i] == false){
                str.append(arr[i]);
                flag[i] = true;
                backStacking(arr,flag);
                str.deleteCharAt(str.length() - 1);
                flag[i] = false;
            }
        }
    }
}

/*
ArrayList<String> lists = new ArrayList<>();
    StringBuilder str = new StringBuilder();
    public ArrayList<String> Permutation (String str) {
        // write code here
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        boolean[] arr2 = new boolean[str.length()];
        backstracking(arr,arr2);
        return lists;
    }

    public void backstracking(char[] arr,boolean[] arr2){
        if(str.length() == arr.length){
            lists.add(str.toString());
        }

        for (int i = 0; i < arr.length; i++) {
            if(i > 0 && arr[i] == arr[i - 1] && arr2[i - 1] == false){
                continue;
            }
            if(arr2[i] == false){
                str.append(arr[i]);
                arr2[i] = true;
                backstracking(arr,arr2);
                arr2[i] = false;
                str.deleteCharAt(str.length() - 1);
            }
        }
    }
 */